package ljl.codetop300;

/**
 * 略微一思索，不会，直接放弃，看答案，聪明人
 *
 * 4 平方和定理也就图一乐
 */
public class _279_min_squares {

  /**
   * 幸好我没自己想
   * 我怎么可能会做这道题？
   */
  static class off1 {
    public int numSquares(int n) {
      int[] f = new int[n + 1];
      for (int i = 1; i <= n; i++) {
        int minn = Integer.MAX_VALUE;
        for (int j = 1; j * j <= i; j++) {
          minn = Math.min(minn, f[i - j * j]);
        }
        f[i] = minn + 1;
      }
      return f[n];
    }
  }

  static class copyoff1 {
    public int numSquares(int n) {
      int[] dp = new int[n + 1];
      for (int i = 1; i <= n; i++) {
        int min = Integer.MAX_VALUE;
        // 为什么取等号因为如果是完全平方数就是 0
        for (int j = 1; j * j <= i; j++) {
          // 死记硬背，这里写成 i - j * j 了
          min = Math.min(min, dp[i - j * j]);
        }
        dp[i] = min + 1;
      }
      return dp[n];
    }
  }

  /**
   * 四平方和定理，如果 4^k(8m+7) 结果是 4，每个数至多 4
   * 其它三种情况，1 2 3，需要自己枚举：若是 2，需要从 1 枚举到根号 n，再看是不是完全平方数，如果是，结果 2
   *
   * 你必须得告诉别人有这个定理，别人才有可能写出解法，不然不可能写出来
   * 纯浪费时间
   */
  static class off2 {
    public int numSquares(int n) {
      if (isPerfectSquare(n)) {
        return 1;
      }
      if (checkAnswer4(n)) {
        return 4;
      }
      for (int i = 1; i * i <= n; i++) {
        int j = n - i * i;
        if (isPerfectSquare(j)) {
          return 2;
        }
      }
      return 3;
    }

    public boolean isPerfectSquare(int x) {
      int y = (int) Math.sqrt(x);
      return y * y == x;
    }

    // 判断是否能表示为 4^k*(8m+7)
    public boolean checkAnswer4(int x) {
      while (x % 4 == 0) {
        x /= 4;
      }
      return x % 8 == 7;
    }
  }

  static class copyoff2 {
    public int numSquares(int n) {
      if (square(n)) return 1;
      if (is4(n)) return 4;
      for (int i = 1; i * i <= n; i++) {
        int j = n - i * i;
        if (square(j)) return 2;
      }
      return 3;
    }
    boolean square(int n) {
      int value = (int) Math.sqrt(n);
      return value * value == n;
    }
    boolean is4(int n) {
      while (n % 4 == 0) {
        n /= 4;
      }
      return n % 8 == 7;
    }
  }


}
